package com.wdn.firstchapter;

/**
 * 实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)
 * Created by wangxin on 2015/11/25.
 */
public class IsUnique {
    public static void main(String[] args) {
        IsUnique isUnique = new IsUnique();
        System.out.println(isUnique.isUnique("odod"));
        System.out.println(isUnique.isUnique2("adv"));
        System.out.println(isUnique.isUnique3("abac"));
    }
    public boolean isUnique(String s){
        boolean[] a = new boolean[256];
        int len = s.length();
        for(int i=0; i < len; ++i)
        {
            int v = (int)s.charAt(i);
            if(a[v]) return false;
            a[v] = true;
        }
        return true;
    }

    /**
     * 字符集只是a－z(或是A－Z)，那就更好办了，用位运算只需要一个整型数即可
     * @param str
     * @return
     */
    public boolean isUnique2(String str){
        int checker = 0;
        for (int i = 0; i < str.length(); ++i) {
            int val = str.charAt(i) - 'a';
            if ((checker & (1 << val)) > 0) return false;
            checker |= (1 << val);
        }
        return true;
    }

    /**
     * 通过位运算来减少空间的使用量。
     * 用每一位表征相应位置字符的出现。对于ASCII字符，我们需要256位，即一个长度为8的int 数组a即可。
     * 这里的关键是要把字符对应的数字，映射到正确的位上去。比如字符’b’对应的 代码是98，那么我们应该将数组中的哪一位置为1呢？
     * 用98除以32，得到对应数组a的下标： 3。98对32取模得到相应的位：2
     * @param s
     * @return
     */
    public boolean isUnique3(String s)
    {
        int[] a = new int[8];
        int len = s.length();
        for(int i=0; i < len; ++i)
        {
            int v = (int)s.charAt(i);
            int idx = v/32;
            int shift = v%32;
            int tmp = a[idx] & (1 << shift);
            //System.out.println(tmp);
            if(tmp>0) return false;
            a[idx] |= (1 << shift);
        }
        return true;
    }
}
